package leetcode_jz_offer.day15_huisuAndBintree;

import java.util.LinkedList;
import java.util.List;

/**
 * 给你二叉树的根节点root和一个整数目标和targetSum，
 * 找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
 * 叶子节点是指没有子节点的节点
 **/
public class Num34_二叉树中和为某一值的路径 {
    private class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    LinkedList<List<Integer>> res=new LinkedList<>();//记录最终结果：所有符合条件的路径
    LinkedList<Integer> path=new LinkedList<>();//遍历到的符合条件的某个路径
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        recur(root,target);
        return res;
    }

    private void recur(TreeNode root, int target) {
        //1.递归终止条件：root==null
        if(root==null){
            return;
        }
        //2.将当前根节点的值加入路径，同时target减去根节点的值。
        // 当根节点值归零同时左右子树为空，则当前节点就是叶子节点且满足所有值和等于target（因为target减完所有节点值自己值就归零，以此判断相等）
          //此时该路径就是结点和为target的路径之一，将该路径加入结果集res中
        path.add(root.val);
        target=target-root.val;
        if(target==0&&root.left==null&&root.right==null){
            res.add(new LinkedList<>(path));
        }
        //3.遍历左右子树
        recur(root.left,target);
        recur(root.right,target);
        //4.回溯计算是否有其他对应路径时应先将当前节点从路径path中删除
        path.removeLast();
    }
}
